1. Field of the Invention
The present invention relates generally to rate conversion of digital data and specifically with the use of poly-phase filters for rate conversion.
2. Related Art
Data is often manifested as discrete time data, that is a representative sample is presented at a given rate. Digital data goes further and each sample is quantized to a digital value. While some data is derived purely digitally, such as the results from a computation by the process, other data is associated with an original analog form, such as audio or video. The analog signal is sampled at the given rate to convert it to a discrete time or digital data. This rate is known as the sampling rate. For example, in audio applications, 44.1 kHz and 48 kHz are common sampling rates.
The process of converting between two sampling rates is known as rate conversion. If the rate conversion goes from a lower rate to a higher rate, it is referred to as upsampling or interpolation. If the rate conversion goes from a higher rate to a lower rate, it is referred to as downsampling or decimation.
FIG. 1 illustrates a typical rate conversion system using a traditional rate converter for a rational rate conversion. In this example, the output is sampled at a rate of L/M times the input sampling rate. The input is signal is first upsampled to the least common multiple of the input and output sampling rate by upsampler 102. Upsampler 102 typically inserts zeroes between the input samples to increase the sampling rate in a process known as zero-padding. This converts the input signal to an upsampled signal at L times the sampling rate. The upsampled signal is then filtered using filter 104 which is a usually a low pass filter. The filter smoothes out the upsampled signal and also prevents aliasing from the downsampling process which is performed by downsampler 106. Typically, downsampler 106 uses decimation to convert from the higher intermediate rate to the lower output rate. The result is a signal that has been downsampled by a factor of M or a total rate change by a factor of L/M.
FIGS. 2A-2D illustrate an example of a rate conversion by 3/2. Graph 202 shows an input signal at a sampling rate that is 2f, where f represents a common sampling rate. Since this example merely expresses sampling rates with a relative rate conversion of 3/2 the specific value of f is not important. Graph 204 the signal is upsampled to 6f by zero-padding. This might be performed by upsampler 102 of system 100. Graph 206 shows the signal after being filtered possibly by a filter like filter 104. Graph 208 shows the signal after resampling or downconversion by a downsampler such as downsampler 106. This is done by decimation. It can be seen that for this 2-1 downconversion, every other 6f sample is discarded to obtain a 3f signal.
One difficulty with this approach is that it relies on finding a reasonable least common multiple. In the case of going from 2f to 3f, a least common multiple of 6f is used. However, in many situations, the least common multiple is not so small. For example to rate convert between to common audio sampling rates 44.1 kHz used by conventional CD and 48 kHz used by other digital audio standards including DVDs, the least common multiple is 7.056 MHz. Rate conversion from 44.1 kHz and 48 kHz would require a 160/147 rate conversion. One key challenge is that the low pass filter would have to operate at 7.056 Mhz which is more than 100 times the sampling rate either input or output operate at. Furthermore, the bandwidth of the filter should be the minimum of the two rates 44.1 kHz and 48 kHz, and the digital filter would typically require 5000-10000 filter coefficients.
One approach to simplify and reduce the demands on resources is to use poly-phase filters. To demonstrate how poly-phase filters can be used, the rate conversion example of FIGS. 2A-2D is used. Suppose a finite impulse response (FIR) filter with an impulse response length of 6 which has 6 filter coefficients is used. It should be noted that in this example, 6 filter coefficients are used for simplicity, but in practice many more coefficients are usually required. Mathematically, this can be summed up as
                                                        y              ′                        ⁡                          [              n              ]                                =                                    ∑                              k                =                0                            5                        ⁢                                                  ⁢                                          h                ⁡                                  [                  k                  ]                                            ⁢                                                x                  ′                                ⁡                                  [                                      n                    -                    k                                    ]                                                                    ,                            (        1        )            where x′[n] is the input signal upsampled to 6f and y′[n] is the filtered signal before downconversion.
FIG. 3 illustrates a conventional FIR filter for implementing equation (1). The input x′[n] is fed through a delay line shown by delay elements 302, 304, 306, 308 and 310. The filter coefficients are applied by scaling elements 312, 314, 316, 318, 320, and 322. The results are summed up by adders 332, 334, 336, 338, and 340. One of ordinary skill in the art will understand that there are many optimizations and equivalent structures. The difficulty in this particular design in a rate converter not only is in the size of the filter, but the delay lines, scaling elements, and adders must operate at the high common multiple sampling rate. While in the given example, the components only operate at a threefold rate, which may not be considered a serious obstacle, in some practical conversion ratios, such the 44.1 kHz to 48 kHz conversion, where an increase in performance of components of over two order of magnitude would be required. This could drastically increase the cost of the components.
To further observe how to derive a poly-phase filter implementation of a rate converter. The first few terms of equation (1), are expanded and can be expressed by equations in (2).
                                                        y              ′                        ⁡                          [              0              ]                                =                                                                      x                  ′                                ⁡                                  [                  0                  ]                                            ⁢                              h                ⁡                                  [                  0                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    1                                    ]                                            ⁢                              h                ⁡                                  [                  1                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    2                                    ]                                            ⁢                              h                ⁡                                  [                  2                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    3                                    ]                                            ⁢                              h                ⁡                                  [                  3                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    4                                    ]                                            ⁢                              h                ⁡                                  [                  4                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    5                                    ]                                            ⁢                              h                ⁡                                  [                  5                  ]                                                                    ⁢                                  ⁢                                            y              ′                        ⁡                          [              1              ]                                =                                                                      x                  ′                                ⁡                                  [                  1                  ]                                            ⁢                              h                ⁡                                  [                  0                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  0                  ]                                            ⁢                              h                ⁡                                  [                  1                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    1                                    ]                                            ⁢                              h                ⁡                                  [                  2                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    2                                    ]                                            ⁢                              h                ⁡                                  [                  3                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    3                                    ]                                            ⁢                              h                ⁡                                  [                  4                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    4                                    ]                                            ⁢                              h                ⁡                                  [                  5                  ]                                                                    ⁢                                  ⁢                                            y              ′                        ⁡                          [              2              ]                                =                                                                      x                  ′                                ⁡                                  [                  2                  ]                                            ⁢                              h                ⁡                                  [                  0                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  1                  ]                                            ⁢                              h                ⁡                                  [                  1                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  0                  ]                                            ⁢                              h                ⁡                                  [                  2                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    1                                    ]                                            ⁢                              h                ⁡                                  [                  3                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    2                                    ]                                            ⁢                              h                ⁡                                  [                  4                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    3                                    ]                                            ⁢                              h                ⁡                                  [                  5                  ]                                                                    ⁢                                  ⁢                                            y              ′                        ⁡                          [              3              ]                                =                                                                      x                  ′                                ⁡                                  [                  3                  ]                                            ⁢                              h                ⁡                                  [                  0                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  2                  ]                                            ⁢                              h                ⁡                                  [                  1                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  1                  ]                                            ⁢                              h                ⁡                                  [                  2                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  0                  ]                                            ⁢                              h                ⁡                                  [                  3                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    1                                    ]                                            ⁢                              h                ⁡                                  [                  4                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    2                                    ]                                            ⁢                              h                ⁡                                  [                  5                  ]                                                                    ⁢                                  ⁢                                            y              ′                        ⁡                          [              4              ]                                =                                                                      x                  ′                                ⁡                                  [                  4                  ]                                            ⁢                              h                ⁡                                  [                  0                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  3                  ]                                            ⁢                              h                ⁡                                  [                  1                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  2                  ]                                            ⁢                              h                ⁡                                  [                  2                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  1                  ]                                            ⁢                              h                ⁡                                  [                  3                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  0                  ]                                            ⁢                              h                ⁡                                  [                  4                  ]                                                      +                                                            x                  ′                                ⁡                                  [                                      -                    1                                    ]                                            ⁢                              h                ⁡                                  [                  5                  ]                                                                    ⁢                                  ⁢                                            y              ′                        ⁡                          [              5              ]                                =                                                                      x                  ′                                ⁡                                  [                  5                  ]                                            ⁢                              h                ⁡                                  [                  0                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  4                  ]                                            ⁢                              h                ⁡                                  [                  1                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  3                  ]                                            ⁢                              h                ⁡                                  [                  2                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  2                  ]                                            ⁢                              h                ⁡                                  [                  3                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  1                  ]                                            ⁢                              h                ⁡                                  [                  4                  ]                                                      +                                                            x                  ′                                ⁡                                  [                  0                  ]                                            ⁢                                                h                  ⁡                                      [                    5                    ]                                                  .                                                                        (        2        )            
As noted above x′[i] is derived from zero padding x[j], which can be expressed by equation (3).
                                          x            ′                    ⁡                      [            n            ]                          =                  {                                                                                          x                    ⁡                                          [                                              n                        3                                            ]                                                        ,                                                                              if                  ⁢                                                                          ⁢                  n                  ⁢                                                                          ⁢                  is                  ⁢                                                                          ⁢                  divisible                  ⁢                                                                          ⁢                  by                  ⁢                                                                          ⁢                  3                                                                                                      0                  ,                                                            otherwise                                                                        (        3        )            Because of the zero padding in equation (3) it should be noted that all x′[n] terms in (2) are zero except for x′[−3], x′[0] and x′[3]. By substituting equation (3) into (2) results in the following simplified series of equations:
                                                        y              ′                        ⁡                          [              0              ]                                =                                                                                          x                    ′                                    ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    0                    ]                                                              +                                                                    x                    ′                                    ⁡                                      [                                          -                      3                                        ]                                                  ⁢                                  h                  ⁡                                      [                    3                    ]                                                                        =                                                            x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    0                    ]                                                              +                                                x                  ⁡                                      [                                          -                      1                                        ]                                                  ⁢                                  h                  ⁡                                      [                    3                    ]                                                                                      ⁢                                  ⁢                                            y              ′                        ⁡                          [              1              ]                                =                                                                                          x                    ′                                    ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    1                    ]                                                              +                                                                    x                    ′                                    ⁡                                      [                                          -                      3                                        ]                                                  ⁢                                  h                  ⁡                                      [                    4                    ]                                                                        =                                                            x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    1                    ]                                                              +                                                x                  ⁡                                      [                                          -                      1                                        ]                                                  ⁢                                  h                  ⁡                                      [                    4                    ]                                                                                      ⁢                                  ⁢                                            y              ′                        ⁡                          [              2              ]                                =                                                                                          x                    ′                                    ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    2                    ]                                                              +                                                                    x                    ′                                    ⁡                                      [                                          -                      3                                        ]                                                  ⁢                                  h                  ⁡                                      [                    5                    ]                                                                        =                                                            x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    2                    ]                                                              +                                                x                  ⁡                                      [                                          -                      1                                        ]                                                  ⁢                                  h                  ⁡                                      [                    5                    ]                                                                                      ⁢                                  ⁢                                            y              ′                        ⁡                          [              3              ]                                =                                                                                          x                    ′                                    ⁡                                      [                    3                    ]                                                  ⁢                                  h                  ⁡                                      [                    0                    ]                                                              +                                                                    x                    ′                                    ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    3                    ]                                                                        =                                                            x                  ⁡                                      [                    1                    ]                                                  ⁢                                  h                  ⁡                                      [                    0                    ]                                                              +                                                x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    3                    ]                                                                                      ⁢                                  ⁢                                            y              ′                        ⁡                          [              4              ]                                =                                                                                          x                    ′                                    ⁡                                      [                    3                    ]                                                  ⁢                                  h                  ⁡                                      [                    1                    ]                                                              +                                                                    x                    ′                                    ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    4                    ]                                                                        =                                                            x                  ⁡                                      [                    1                    ]                                                  ⁢                                  h                  ⁡                                      [                    1                    ]                                                              +                                                x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    4                    ]                                                                                      ⁢                                  ⁢                                            y              ′                        ⁡                          [              5              ]                                =                                                                                          x                    ′                                    ⁡                                      [                    3                    ]                                                  ⁢                                  h                  ⁡                                      [                    2                    ]                                                              +                                                                    x                    ′                                    ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    5                    ]                                                                        =                                                            x                  ⁡                                      [                    1                    ]                                                  ⁢                                  h                  ⁡                                      [                    2                    ]                                                              +                                                x                  ⁡                                      [                    0                    ]                                                  ⁢                                                      h                    ⁡                                          [                      5                      ]                                                        .                                                                                        (        4        )            Because the final output downsamples y′ into y, the decimation process can be expressed simply as:y[n]=y′[2n].  (5)
This reduces equations in (4) into the following series of equations:
                                          y            ⁡                          [              0              ]                                =                                                    y                ′                            ⁡                              [                0                ]                                      =                                                            x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    0                    ]                                                              +                                                x                  ⁡                                      [                                          -                      1                                        ]                                                  ⁢                                  h                  ⁡                                      [                    3                    ]                                                                                      ⁢                                  ⁢                              y            ⁡                          [              1              ]                                =                                                    y                ′                            ⁡                              [                2                ]                                      =                                                            x                  ⁡                                      [                    0                    ]                                                  ⁢                                  h                  ⁡                                      [                    2                    ]                                                              +                                                x                  ⁡                                      [                                          -                      1                                        ]                                                  ⁢                                  h                  ⁡                                      [                    5                    ]                                                                                      ⁢                                  ⁢                              y            ⁡                          [              2              ]                                =                                                    y                ′                            ⁡                              [                4                ]                                      =                                                            x                  ⁡                                      [                    1                    ]                                                  ⁢                                  h                  ⁡                                      [                    1                    ]                                                              +                                                x                  ⁡                                      [                    0                    ]                                                  ⁢                                                      h                    ⁡                                          [                      4                      ]                                                        .                                                                                        (        6        )            
Comparing the equations for a general filter in (2) and the final simplified equations in (6), it can be seen that the number of calculations and complexity can be greatly reduced. FIG. 4 shows a corresponding poly-phase architecture. Rate converter 400 comprises delay line 402 which now operates at the input sampling rate 2f. Scaling elements 404 and 406 as well as adder 408 operate at the output sampling rate 3f. Scaling elements 404 and 406 apply the filter coefficient similarly to the scaling elements in FIG. 3 except the filter coefficients change. Hence the coefficients are presented by hi[n] rather than simply h[n], where the index i changes with the index of the output sample at output sampling rate 3f. In the specific example given above, hi[1] cycles through the coefficients h[3], h[5], and h[4], and hi[0] cycles through the coefficients h[0], h[2], and h[1]. The poly-phase architecture has many advantages in that fewer operations take place and the components can operate at a lower sampling rate.
FIG. 5 shows a generalized poly-phase architecture for rate conversion. Rate converter 500 comprises a delay line having a plurality of delay elements shown by representative delay elements 502, 504, and 506, which operate at the input sampling rate. A plurality of scaling elements shown by representative scaling elements 512, 514, 516 and 518 apply filter coefficients hi[n] where the index i changes at the output sampling rate. The results are summed together either by one or more adders shown here by adders 522, 524 and 526. In this example only representative stages are shown, but it should be understood that this and subsequent diagrams are intended to illustrate a generalized N-stage architecture.
One difficulty with the traditional use of poly-phase filters is that the design relics on a fixed input and output sampling rate. It is not suitable for changing rates. Furthermore, it still relies on a rational relationship between the input and output sampling rates. In the case of an incommensurate ratio between sampling rates, the traditional poly-phase rate converter cannot be applied.
FIG. 6 shows the use of a Farrow architecture for handling incommensurate ratios. The input signal is buffered by input module 602 which serves as a buffer to hold the input to the next integer cycle of the output sample rate. It also calculates the fractional delay of the output sample, this fractional delay is shown as d. The buffered input is passed through a plurality of linear filters represented by filters 612, 614, 616, 618, and 620, at each stage a running sum is calculated where each previous stage is multiplied by the fractional delay. The multiplication are shown in this example as performed by scaling elements 628, 626, 624 and 622. The running sums are shown here as performed by 632, 634, 636 and 638. Essentially, this structure evaluates a polynomial in the fractional difference, where the polynomial coefficients are actually linear filters. The primary difficulty in this approach is that it has high computational load and it is inflexible because the filter coefficients for all the filters must be calculated offline beforehand. In particular, it does not allow flexibility in tradeoff between complexity and quality once the filter coefficients have been designed.
Therefore, there is a need in the industry for a flexible rate converter that is computational efficient.